package cn.com.forever.offer;

/*
    描述
    我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？

    比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：
 */

public class 矩形覆盖 {
    public static void main(String[] args) {
        System.out.println(rectCover(4));
    }

    public static int rectCover(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        int[] dp = new int[target+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= target; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[target];
    }
}
